//树
#ifndef __TREE__HPP
#define __TREE__HPP

#include"../Universal.h"

namespace NgSiuKei {

//注意：
//因为普通的树结构很难让使用者定位所有节点位置，
//也就是说实际上只有`树`的`根节点`是可以操作的，
//所以不封装什么JB类了，直接操作根节点
//🍀

template<class TheClass>
struct tree_node;

//子树链表节点
template<class TheClass>
struct child_tree_list_node {
    tree_node<TheClass> *tree;
    child_tree_list_node<TheClass> *next;
};

//树节点
template<class TheClass>
struct tree_node {
    TheClass val;
    tree_node<TheClass> *parent;
    U_L_L childNum;
    child_tree_list_node<TheClass> *childs;
};

//构造
template<class TheClass>
tree_node<TheClass> *createTree(const TheClass val, child_tree_list_node<TheClass> * const subTrees) {
    tree_node<TheClass> *tree = new tree_node<TheClass>;
    tree->val = val;
    tree->parent = nullptr;
    if(nullptr != subTrees) {
        U_L_L subTreeNum = 1;
        const child_tree_list_node<TheClass> *tempSubTrees = subTrees;
        while(nullptr != tempSubTrees) {
            tempSubTrees = tempSubTrees->next;
            subTreeNum++;
        }
        tree->childNum = subTreeNum;
        tree->childs = subTrees;
    }
    else {
        tree->childNum = 0;
        tree->childs = nullptr;
    }
    return tree;
}

//清空
template<class TheClass>
void clearTree(tree_node<TheClass> *&tree) {
    if(nullptr == tree) {
        return;
    }

    if(nullptr != tree->childs) {
        child_tree_list_node<TheClass> *currentChild = tree->childs;
        while(nullptr != currentChild) {
            clearTree(currentChild->tree);
            currentChild = currentChild->next;
        }

    }
    delete tree;
    tree = nullptr;
}

//插入子树
template<class TheClass>
void insertSubTree(tree_node<TheClass> * const tree, tree_node<TheClass> * const subTree) {
    if(nullptr == tree || nullptr == subTree) {
        return;
    }

    subTree->parent = tree;

    child_tree_list_node<TheClass> *newChild = new child_tree_list_node<TheClass>;
    newChild->tree = subTree;
    newChild->next = nullptr;

    if(0 == tree->childNum) {
        tree->childs = newChild;
    }
    else {
        child_tree_list_node<TheClass> *currentChild = tree->childs;
        while(nullptr != currentChild->next) {
            currentChild = currentChild->next;
        }
        currentChild->next = newChild;
    }
    tree->childNum++;
}

//获取高度
template<class TheClass>
U_L_L getTreeHeight(const tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return 0;
    }
    U_L_L childTreeHeight = 0;
    U_L_L tempHeight;
    child_tree_list_node<TheClass> *currentChildNode = tree->childs;
    while(nullptr != currentChildNode) {
        tempHeight = getTreeHeight(currentChildNode->tree);
        childTreeHeight = (childTreeHeight<tempHeight)?(tempHeight):(childTreeHeight);
        currentChildNode = currentChildNode->next;
    }
    return 1+childTreeHeight;
}

//获取节点数量
template<class TheClass>
U_L_L getTreeNodeNum(const tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return 0;
    }
    U_L_L num = 1;
    child_tree_list_node<TheClass> *currentChildNode = tree->childs;
    while(nullptr != currentChildNode) {
        num += getTreeNodeNum(currentChildNode->tree);
        currentChildNode = currentChildNode->next;
    }
    return num;
}

//深度优先遍历
template<class TheClass>
TheClass *dfsOrderTree(const tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return nullptr;
    }
    U_L_L nodeNum = getTreeNodeNum(tree);
    TheClass *result = new TheClass[nodeNum];
    U_L_L index = 0;
    dfsOrderTreeToArray(tree, result, index);
    return result;
}

template<class TheClass>
static void dfsOrderTreeToArray(const tree_node<TheClass> *tree, TheClass *&array, U_L_L &index) {
    array[index] = tree->val;
    child_tree_list_node<TheClass> *currentChildNode = tree->childs;
    while(nullptr != currentChildNode) {
        dfsOrderTreeToArray(currentChildNode->tree, array, ++index);
        currentChildNode = currentChildNode->next;
    }
}

//广度优先遍历
template<class TheClass>
TheClass *bfsOrderTree(const tree_node<TheClass> *tree) {
    if(nullptr == tree) {
        return nullptr;
    }
    U_L_L i, j, k;
    U_L_L nodeNum = getTreeNodeNum(tree);
    U_L_L treeHeight = getTreeHeight(tree);
    TheClass **levelVal = new TheClass *[treeHeight];
    U_L_L nodeNumOfEveryLevel[treeHeight]; //记录每一层的节点数量
    for(i=0; i<treeHeight; ++i) {
        levelVal[i] = new TheClass[nodeNum];
        nodeNumOfEveryLevel[i] = 0;
    }

    bfsOrderTreeToArray(tree, levelVal, nodeNumOfEveryLevel, 0);

    TheClass *result = new TheClass[nodeNum];
    k = 0;
    for(i=0; i<treeHeight; ++i) {
        for(j=0; j<nodeNumOfEveryLevel[i]; ++j) {
            result[k++] = levelVal[i][j];
        }
    }
    
    //销毁
    for(i=0; i<treeHeight; ++i) {
        delete levelVal[i];
    }
    delete[] levelVal;

    return result;
}

template<class TheClass>
static void bfsOrderTreeToArray(const tree_node<TheClass> *tree, TheClass **&array, U_L_L *nodeNumOfEveryLevel, U_L_L level) {
    if(nullptr == tree) {
        return;
    }

    array[level][nodeNumOfEveryLevel[level]] = tree->val;
    nodeNumOfEveryLevel[level]++;
    child_tree_list_node<TheClass> *currentChildNode = tree->childs;
    while(nullptr != currentChildNode) {
        bfsOrderTreeToArray(currentChildNode->tree, array, nodeNumOfEveryLevel, level+1);
        currentChildNode = currentChildNode->next;
    }
}

}

#endif